The present invention relates to a load balancing mechanism through collaboration of a plurality of information processing devices, or computers, such as, for example, personal computers and servers.
There are two approaches to load balancing one task through a plurality of computers connected to a network.
One approach is to first determine which computer to load balance and assign the content of information processing (hereinafter referred to as “task”) thereto; another approach is such that when the load is found too heavy after a task is executed by a certain computer, a search is conducted for another computer to assign the task thereto.
In the former case, the magnitude of the load of the task must be predicted beforehand; however, for information processing where the magnitude of the load is unpredictable, assignment of tasks cannot be achieved. In the latter case, there is no need for predicting the magnitude of the load; however, once the load is found too heavy, special processing is required to search for another computer having excess computing resources. However, after a computer having excess computing resources is found, if the usage status of that computer changes when a task is actually assigned thereto, it is necessary to search for still another computer having excess computing resources to load balance, thus resulting in complicated procedures accordingly.
Generally, when tasks are executed by a single computing resource within a computer, time sharing process or the like is employed to assign tasks. The degree with which the computing resources are left is determined by how much time is used to complete the task as the task is partitioned by a certain time unit. FIG. 12(a) illustrates this situation.
However, because the time unit to partition the task differs depending on the type of task, it is difficult to predict whether another task can be assigned to the spare time. Furthermore, if the unit time is aligned forcefully, the overhead due to task switching becomes greater, thus resulting in more difficulty in prediction.
FIG. 12(b) illustrates a timing example where a plurality of tasks are executed by a single processor via time sharing. In the example of FIG. 12(b), after task A completes one unit of processing, another task is assigned for a certain time (during which task A has a spare time); after a certain time, task A is repeated again. In this case, if one unit of processing of task A is always assured to be completed in a certain time, a percentage of task A occupying the overall processing time is conveniently fixed; however, if it is not completed within a certain time due to task execution conditions, the percentage of processing time for task A varies, as shown in FIG. 12(c). Cases where the processing time varies due to task execution conditions include examples where the number of objects to be drawn varies when the viewpoint moves during graphic processing, and where whether to use preceding and/or succeeding frames of data varies depending upon the image content during decompression of a compressed video image. “One unit of processing” in such cases includes one frame worth of processing, for example.
To solve the inconvenience associated with varying percentage of processing time due to task execution conditions as described above, one conceivable scenario is to partition one unit of processing into smallest time intervals as possible and abort task A after a certain time has elapsed. In this case, the situation may occur, as shown in FIG. 12(d), where the task must be switched at switching timing A, instead of switching timing B where the task can be switched conveniently. In that case, unless much more data (context) is saved, the task cannot be resumed. This data saving/loading could adversely result in processing overhead.
Accordingly, with the methods for assigning a plurality of tasks by a single processor via timing sharing, it is difficult to achieve both stability of assigned time and efficiency in processing.
The present invention has its main objective to provide a distributed information processing mechanism that solves the afore-described prior art problem.